#include "integer.h"
#include "../arch/asm.h"
#include "../base/logger.h"

OPEN_JLIB_NS


Integer::Num Integer::__One = {1L};
Integer::Num Integer::__Ten = {10L};
u64 Integer::__counter = 0;
u64 Integer::Num::__counter = 0;


void Integer::__and (u32* dst, const u32* op1, u32 len1, const u32* op2, u32 len2) noexcept {
  s32 i = 0;
  for (; i < len2; ++i)
    dst[i] = op1[i] & op2[i];
  for (; i < len1; ++i)
    dst[i] = 0;
}

void Integer::__andn (u32* dst, const u32* op1, u32 len1, const u32* op2, u32 len2) noexcept {
  s32 i = 0;
  for (; i < len2; ++i)
    dst[i] = ~(op1[i] & op2[i]);
  for (; i < len1; ++i)
    dst[i] = 0xFFFFFFFF;
}

void Integer::__or (u32* dst, const u32* op1, u32 len1, const u32* op2, u32 len2) noexcept {
  s32 i = 0;
  for (; i < len2; ++i)
    dst[i] = op1[i] | op2[i];
  for (; i < len1; ++i)
    dst[i] = op1[i];
}

void Integer::__orn (u32* dst, const u32* op1, u32 len1, const u32* op2, u32 len2) noexcept {
  s32 i = 0;
  for (; i < len2; ++i)
    dst[i] = ~(op1[i] | op2[i]);
  for (; i < len1; ++i)
    dst[i] = ~op1[i];
}

void Integer::__xor (u32* dst, const u32* op1, u32 len1, const u32* op2, u32 len2) noexcept {
  s32 i = 0;
  for (; i < len2; ++i)
    dst[i] = op1[i] ^ op2[i];
  for (; i < len1; ++i)
    dst[i] = op1[i];
}

void Integer::__xorn (u32* dst, const u32* op1, u32 len1, const u32* op2, u32 len2) noexcept {
  s32 i = 0;
  for (; i < len2; ++i)
    dst[i] = ~(op1[i] ^ op2[i]);
  for (; i < len1; ++i)
    dst[i] = ~op1[i];
}

void Integer::__not (u32* dst, const u32* src, u32 len) noexcept {
  for (s32 i = 0; i < len; ++i)
    dst[i] = ~src[i];
}

u32 Integer::__shl (u32* dst, const u32* src, u32 len, u32 shift) noexcept {
  if (!shift) {
    memcpy(dst, src, len << 2);
    return 0;
  }
  dst[0] = src[0] << shift;
  shift = 32 - shift;
  for (s32 i = 1; i < len; ++i)
    dst[i] = u32(((u64(src[i]) << 32) | src[i - 1]) >> shift);
  return src[len - 1] >> shift;
}

u32 Integer::__shr (u32* dst, const u32* src, u32 len, u32 shift) noexcept {
  if (!shift) {
    memcpy(dst, src, len << 2);
    return 0;
  }
  dst[len - 1] = src[len - 1] >> shift;
  for (s32 i = len - 2; i >= 0; --i)
    dst[i] = u32(((u64(src[i + 1]) << 32) | src[i]) >> shift);
  return src[0] << (32 - shift);
}


s32 Integer::__cmp (const u32* op1, u32 len1, const u32* op2, u32 len2) noexcept {
  debug_assert(op1 && len1);
  debug_assert(op2 && len2);
  if (len1 > len2)
    return 1;
  if (len1 < len2)
    return -1;
  for (s32 i = len1 - 1; i >= 0; --i) {
    if (op1[i] > op2[i])
      return 1;
    if (op1[i] < op2[i])
      return -1;
  }
  return 0;
}


u32 Integer::__add (u32* dst, const u32* op1, u32 len1, u32 op2) noexcept {
  debug_assert(op1 && len1);
  u64 sum = u64(op1[0]) + op2;
  dst[0] = u32(sum);
  u64 carry = sum >> 32;
  u32 i = 1;
  for (; carry && i < len1; ++i) {
    sum = carry + op1[i];
    dst[i] = u32(sum);
    carry = sum >> 32;
  }
  for (; i < len1; ++i)
    dst[i] = op1[i];
  return u32(carry);
}

u32 Integer::__add (u32* dst, const u32* op1, u32 len1, const u32* op2, u32 len2) noexcept {
  debug_assert(op1 && len1);
  debug_assert(op2 && len2);
  debug_assert(len1 >= len2);
  u64 sum = u64(op1[0]) + op2[0];
  dst[0] = u32(sum);
  u64 carry = sum >> 32;
  u32 i = 1;
  for (; i < len2; ++i) {
    sum = carry + op1[i] + op2[i];
    dst[i] = u32(sum);
    carry = sum >> 32;
  }
  for (; carry && i < len1; ++i) {
    sum = carry + op1[i];
    dst[i] = u32(sum);
    carry = sum >> 32;
  }
  for (; i < len1; ++i)
    dst[i] = op1[i];
  return u32(carry);
}


s32 Integer::__sub (u32* dst, const u32* op1, u32 len1, u32 op2) noexcept {
  debug_assert(op1 && len1);
  s64 difference = u64(op1[0]) - op2;
  dst[0] = u32(difference);
  s64 borrow = difference >> 32;
  u32 i = 1;
  for (; borrow && i < len1; ++i) {
    difference = borrow + op1[i] - op2;
    dst[i] = u32(difference);
    borrow = difference >> 32;
  }
  for (; i < len1; ++i)
    dst[i] = op1[i];
  return s32(borrow);
}

s32 Integer::__sub (u32* dst, const u32* op1, u32 len1, const u32* op2, u32 len2) noexcept {
  debug_assert(op1 && len1);
  debug_assert(op2 && len2);
  debug_assert(len1 >= len2);
  s64 difference = u64(op1[0]) - op2[0];
  dst[0] = u32(difference);
  s64 borrow = difference >> 32;
  u32 i = 1;
  for (; i < len2; ++i) {
    difference = borrow + op1[i] - op2[i];
    dst[i] = u32(difference);
    borrow = difference >> 32;
  }
  for (; borrow && i < len1; ++i) {
    difference = borrow + op1[i];
    dst[i] = u32(difference);
    borrow = difference >> 32;
  }
  for (; i < len1; ++i)
    dst[i] = op1[i];
  return u32(borrow);
}


u32 Integer::__mul (u32* dst, const u32* op1, u32 len1, u32 op2) noexcept {
  debug_assert(op1 && len1);
  u64 product = u64(op1[0]) * op2;
  dst[0] = u32(product);
  u64 carry = product >> 32;
  u32 i = 1;
  for (; i < len1; ++i) {
    product = carry + u64(op1[i]) * op2;
    dst[i] = u32(product);
    carry = product >> 32;
  }
  return u32(carry);
}

void Integer::__mul (u32* dst, const u32* op1, u32 len1, const u32* op2, u32 len2) noexcept {
  debug_assert(op1 && len1);
  debug_assert(op2 && len2);
  u64 product, carry = 0;
  uwl i, j, k;
  for (i = 0; i < len1; ++i) {
    product = carry + u64(op1[i]) * op2[0];
    dst[i] = u32(product);
    carry = product >> 32;
  }
  dst[i] = u32(carry);
  for (j = 1; j < len2; ++j) {
    carry = 0;
    if (op2[j]) {
      for (k = j, i = 0; i < len1; ++i, ++k) {
        product = carry + dst[k] + u64(op1[i]) * op2[j];
        dst[k] = u32(product);
        carry = product >> 32;
      }
    }
    dst[j + len1] = u32(carry);
  }
}


u32 Integer::__div (u32* dst, const u32* op1, u32 len1, u32 op2) noexcept {
  debug_assert(op1 && len1);
  u32 q, r = 0;
  for (s32 i = len1 - 1; i >= 0; --i) {
    q = op1[i];
    __udiv(q, r, op2);
    if (dst)
      dst[i] = q;
  }
  return r;
}

void Integer::__div (u32* dst, u32* mod, const u32* op1, u32 len1, const u32* op2, u32 len2) noexcept {
  debug_assert(op1 && len1);
  debug_assert(op2 && len2);
  debug_assert(len1 >= len2);
  u32 shift = __leading_zeros(op2[len2 - 1]);
  Num* A = Num::allocate(len1 + 1);
  Num* B = Num::allocate(len2 + 1);
  Num* C = Num::allocate(len2 + 1);
  A->data[len1] = __shl(A->data, op1, len1, shift);
  A->size = len1 + 1;
  B->data[len2] = __shl(B->data, op2, len2, shift);
  B->size = len2;
  u64 b_1 = B->data[len2 - 1];
  u64 b_2 = B->data[len2 - 2];
  for (s32 i = len1 - len2; i >= 0; --i) {
    u64 r = 0;
    u64 q = (u64(A->data[i + len2]) << 32) | A->data[i + len2 - 1];
    u64 a_2 = A->data[i + len2 - 2];
    __udiv(q, r, b_1);
    while (q == 0x100000000UL || q * b_2 > (r << 32) + a_2) {
      q -= 1;
      r += b_1;
      if (r >= 0x100000000UL)
        break;
    }
    C->data[len2] = __mul(C->data, B->data, len2, u32(q));
    C->size = len2 + 1;
    s32 borrow = __sub(A->data + i, A->data + i, len2 + 1, C->data, len2 + 1);
    if (borrow) {
      q -= 1;
      __add(A->data + i, A->data + i, len2 + 1, B->data, len2);
    }
    if (dst)
      dst[i] = u32(q);
  }
  if (mod)
    __shr(mod, A->data, len2, shift);
  A->release();
  B->release();
  C->release();
}


u32 Integer::__check_digit (const c8* src) noexcept {
  u32 i = 0;
  for (; src[i]; ++i)
    if (src[i] < '0' || '9' < src[i])
      break;
  return i;
}

u32 Integer::__check_digit (const c8* src, u32 len) noexcept {
  for (u32 i = 0; i < len; ++i)
    if (src[i] < '0' || '9' < src[i])
      return i;
  return len;
}

s32 Integer::__encode_sign (c8 src) noexcept {
  if (src == '-')
    return -1;
  if (src == '+')
    return 1;
  return 0;
}

u32 Integer::__encode_digit (const c8* src, u32 len) noexcept {
  static const u32 coefficient[] = {100000000,10000000,1000000,100000,10000,1000,100,10};
  u32 res = u32(src[--len] - '0');
  for (uwl i = 0, j = 8 - len; i < len; ++i, ++j)
    res += u32(src[i] - '0') * coefficient[j];
  return res;
}

void Integer::__decode_digit (std::string& dst, Num* src) noexcept {
  u32 q = __div(src->data, src->data, src->size, 1000000000U);
  src->shrink(src->size);

  c8 buf[9];
  u32 i = 9;
  while (q) {
    u32 r = 0;
    __udiv(q, r, 10U);
    buf[--i] = c8(r + '0');
  }

  if (src->size) {
    while (i)
      buf[--i] = '0';
    __decode_digit(dst, src);
    dst.append(buf, 9);
  }
  else {
    dst.append(buf + i, 9 - i);
  }
}


Integer::Integer (s64 src) noexcept {
  ++__counter;
  if (src == 0) {
    _num = nullptr;
    _sig = 0;
    return;
  }
  if (src < 0) {
    _sig = -1;
    src = -src;
  }
  else {
    _sig = 1;
  }
  switch (src) {
    case 1L:
      _num = &__One;
      _num->retain();
      break;
    case 10L:
      _num = &__Ten;
      _num->retain();
      break;
    default:
      _num = Num::allocate(2);
      _num->data[0] = u32(src);
      _num->data[1] = u32(src >> 32);
      _num->shrink(2);
  }
}

Integer::Integer (const c8* src) noexcept {
  ++__counter;
  for (; src;) {
    s32 sign = __encode_sign(*src);
    if (sign)
      ++src;
    for (; *src == '0'; ++src);
    u32 size = __check_digit(src);
    if (!size)
      break;
    u32 b = ((size * 3402) >> 10) + 1;
    u32 n = (b + 31) >> 5;
    u32 r = 0;
    u32 q = size;
    __udiv(q, r, 9U);
    if (!r) {
      r = 9;
      q -= 1;
    }
    Num* num = Num::allocate(n);
    num->data[0] = __encode_digit(src, r);
    num->size = 1;
    src += r;
    for (u32 i = 0; i < q; ++i, src += 9) {
      u32 a = __encode_digit(src, 9);
      u32 c = __mul(num->data, num->data, num->size, 1000000000U);
      c += __add(num->data, num->data, num->size, a);
      if (c)
        num->data[num->size++] = c;
    }
    _num = num;
    _sig = sign < 0 ? -1 : 1;
    return;
  }
  _num = nullptr;
  _sig = 0;
}

Integer::Integer (const c8* src, u32 len) noexcept {
  ++__counter;
  for (; src && len;) {
    s32 sign = __encode_sign(*src);
    if (sign) {
      ++src;
      --len;
    }
    for (; len && *src == '0'; ++src, --len);
    u32 size = __check_digit(src, len);
    if (!size)
      break;
    u32 b = ((size * 3402) >> 10) + 1;
    u32 n = (b + 31) >> 5;
    u32 r = 0;
    u32 q = size;
    __udiv(q, r, 9U);
    if (!r) {
      r = 9;
      q -= 1;
    }
    Num* num = Num::allocate(n);
    num->data[0] = __encode_digit(src, r);
    num->size = 1;
    src += r;
    for (u32 i = 0; i < q; ++i, src += 9) {
      u32 a = __encode_digit(src, 9);
      u32 c = __mul(num->data, num->data, num->size, 1000000000U);
      c += __add(num->data, num->data, num->size, a);
      if (c)
        num->data[num->size++] = c;
    }
    _num = num;
    _sig = sign < 0 ? -1 : 1;
    return;
  }
  _num = nullptr;
  _sig = 0;
}


std::string Integer::str (bool sign) const noexcept {
  std::string res;
  if (_sig < 0)
    res += '-';
  else if (sign)
    res += '+';
  if (!_sig) {
    res += '0';
    return res;
  }
  Num* A = Num::allocate(_num->size);
  A->size = _num->size;
  memcpy(A->data, _num->data, A->size << 2);
  __decode_digit(res, A);
  A->release();
  return res;
}


s32 Integer::msb () const noexcept {
  if (_sig == 0)
    return -1;
  for (s32 i = _num->size - 1; i >= 0; --i) {
    if (_num->data[i] != 0)
      return i * 32 + 31 - __leading_zeros(_num->data[i]);
  }
  return -1;
}

s32 Integer::lsb () const noexcept {
  if (_sig == 0)
    return -1;
  for (s32 i = 0; i < _num->size; ++i) {
    if (_num->data[i] != 0)
      return i * 32 + __trailing_zeros(_num->data[i]);
  }
  return -1;
}


s32 Integer::cmp (const Integer& other) const noexcept {
  auto sdiff = _sig - other._sig;
  if (sdiff)
    return sdiff > 0 ? 1 : -1;
  if (_sig == 0)
    return 0;
  auto op1 = _num;
  auto op2 = other._num;
  return _sig * __cmp(op1->data, op1->size, op2->data, op2->size);
}


Integer Integer::operator+ (const Integer& other) const noexcept {
  if (!other._sig)
    return {*this};
  if (!_sig)
    return {other};
  auto op1 = _num;
  auto op2 = other._num;
  if (_sig == other._sig) {
    if (op1->size < op2->size)
      __swap(op1, op2);
    auto dst = Num::allocate(op1->size + 1);
    dst->data[op1->size] = __add(dst->data, op1->data, op1->size, op2->data, op2->size);
    dst->shrink(op1->size + 1);
    return {dst, _sig, false};
  }
  else {
    auto res = __cmp(op1->data, op1->size, op2->data, op2->size);
    if (res == 0)
      return {};
    if (res < 0)
      __swap(op1, op2);
    auto dst = Num::allocate(op1->size);
    __sub(dst->data, op1->data, op1->size, op2->data, op2->size);
    dst->shrink(op1->size);
    return {dst, _sig * res, false};
  }
}

Integer Integer::operator- (const Integer& other) const noexcept {
  if (!other._sig)
    return {*this};
  if (!_sig)
    return {other._num, -other._sig};
  auto op1 = _num;
  auto op2 = other._num;
  if (_sig == other._sig) {
    auto res = __cmp(op1->data, op1->size, op2->data, op2->size);
    if (res == 0)
      return {};
    if (res < 0)
      __swap(op1, op2);
    auto dst = Num::allocate(op1->size);
    __sub(dst->data, op1->data, op1->size, op2->data, op2->size);
    dst->shrink(op1->size);
    return {dst, _sig * res, false};
  }
  else {
    if (op1->size < op2->size)
      __swap(op1, op2);
    auto dst = Num::allocate(op1->size + 1);
    dst->data[op1->size] = __add(dst->data, op1->data, op1->size, op2->data, op2->size);
    dst->shrink(op1->size + 1);
    return {dst, _sig, false};
  }
}

Integer Integer::operator* (const Integer& other) const noexcept {
  if (!_sig || !other._sig)
    return {};
  if (_num == &__One)
    return {other._num, _sig * other._sig};
  if (other._num == &__One)
    return {_num, _sig * other._sig};
  auto op1 = _num;
  auto op2 = other._num;
  if (op1->size > op2->size)
    __swap(op1, op2);
  auto dst = Num::allocate(op1->size + op2->size);
  __mul(dst->data, op1->data, op1->size, op2->data, op2->size);
  dst->shrink(op1->size + op2->size);
  return {dst, _sig * other._sig, false};
}

Integer Integer::operator/ (const Integer& other) const {
  if (!other._sig)
    throw "divide by 0";
  if (!_sig)
    return {};
  if (other._num == &__One)
    return {_num, _sig * other._sig};
  auto op1 = _num;
  auto op2 = other._num;
  auto res = __cmp(op1->data, op1->size, op2->data, op2->size);
  if (res < 0)
    return {};
  if (res == 0)
    return {&__One, _sig * other._sig};
  auto dst = Num::allocate(op1->size - op2->size + 1);
  if (op2->size == 1)
    __div(dst->data, op1->data, op1->size, op2->data[0]);
  else
    __div(dst->data, nullptr, op1->data, op1->size, op2->data, op2->size);
  dst->shrink(op1->size - op2->size + 1);
  return {dst, _sig * other._sig, false};
}

Integer Integer::operator% (const Integer& other) const {
  if (!other._sig)
    throw "divide by 0";
  if (!_sig || other._num == &__One)
    return {};
  auto op1 = _num;
  auto op2 = other._num;
  auto res = __cmp(op1->data, op1->size, op2->data, op2->size);
  if (res < 0)
    return {*this};
  if (res == 0)
    return {};
  auto mod = Num::allocate(op2->size);
  if (op2->size == 1) {
    mod->data[0] = __div(nullptr, op1->data, op1->size, op2->data[0]);
    mod->size = 1;
  }
  else {
    __div(nullptr, mod->data, op1->data, op1->size, op2->data, op2->size);
    mod->size = op2->size;
  }
  mod->shrink(mod->size);
  return {mod, mod->size ? _sig : 0, false};
}


Integer Integer::operator- () const noexcept {
  if (!_sig)
    return {};
  return {_num, -_sig};
}

Integer Integer::abs () const noexcept {
  if (_sig == 0)
    return {};
  if (_sig > 0)
    return *this;
  return {_num, -_sig};
}

Integer Integer::pow (u32 exp) const noexcept {
  if (exp == 0)
    return {&__One, 1};
  if (exp == 1)
    return *this;
  if (_sig == 0)
    return {};
  Integer src = abs();
  Integer dst{1L};
  s32 pow2 = src.lsb();
  if (pow2 > 0)
    src = src >> u32(pow2);
  Integer base{src};
  for (u32 texp = exp; texp; texp >>= 1, base = base * base) {
    if (texp & 1)
      dst = dst * base;
  }
  if (pow2 > 0)
    dst = dst << (pow2 * exp);
  if (_sig < 0 && exp & 1)
    dst._sig = -1;
  return dst;
}


Integer Integer::operator& (const Integer& other) const noexcept {
  if (!_sig || !other._sig)
    return {};
  auto op1 = _num;
  auto op2 = other._num;
  if (op1->size < op2->size)
    __swap(op1, op2);
  auto dst = Num::allocate(op1->size);
  __and(dst->data, op1->data, op1->size, op2->data, op2->size);
  dst->shrink(op1->size);
  return {dst, _sig, false};
}

Integer Integer::operator| (const Integer& other) const noexcept {
  if (!_sig)
    return {other._num, _sig};
  if (!other._sig)
    return *this;
  auto op1 = _num;
  auto op2 = other._num;
  if (op1->size < op2->size)
    __swap(op1, op2);
  auto dst = Num::allocate(op1->size);
  __or(dst->data, op1->data, op1->size, op2->data, op2->size);
  dst->size = op1->size;
  return {dst, _sig, false};
}

Integer Integer::operator^ (const Integer& other) const noexcept {
  if (!_sig)
    return {other._num, _sig};
  if (!other._sig)
    return *this;
  auto op1 = _num;
  auto op2 = other._num;
  if (op1->size < op2->size)
    __swap(op1, op2);
  auto dst = Num::allocate(op1->size);
  __xor(dst->data, op1->data, op1->size, op2->data, op2->size);
  dst->shrink(op1->size);
  return {dst, _sig, false};
}

Integer Integer::operator~ () const noexcept {
  if (!_sig)
    return {};
  auto src = _num;
  auto dst = Num::allocate(src->size);
  __not(dst->data, src->data, src->size);
  dst->shrink(src->size);
  return {dst, _sig, false};
}

Integer Integer::operator<< (u32 shift) const noexcept {
  if (!_sig)
    return {};
  u32 ish = shift >> 5;
  auto src = _num;
  auto dst = Num::allocate(src->size + ish + 1);
  dst->data[src->size + ish] = __shl(dst->data + ish, src->data, src->size, shift & 0x1F);
  memset(dst->data, 0, ish << 2);
  dst->shrink(src->size + ish + 1);
  return {dst, _sig, false};
}

Integer Integer::operator>> (u32 shift) const noexcept {
  if (!_sig)
    return {};
  u32 ish = shift >> 5;
  if (ish >= _num->size)
    return {};
  auto src = _num;
  auto dst = Num::allocate(src->size - ish);
  __shr(dst->data, src->data + ish, src->size - ish, shift & 0x1F);
  dst->shrink(src->size - ish);
  return {dst, _sig, false};
}


bool Integer::operator== (const Integer& other) const noexcept {
  if (_sig != other._sig)
    return false;
  if (_sig == 0)
    return true;
  auto op1 = _num;
  auto op2 = other._num;
  return __cmp(op1->data, op1->size, op2->data, op2->size) == 0;
}

bool Integer::operator!= (const Integer& other) const noexcept {
  if (_sig != other._sig)
    return true;
  if (_sig == 0)
    return false;
  auto op1 = _num;
  auto op2 = other._num;
  return __cmp(op1->data, op1->size, op2->data, op2->size) != 0;
}

bool Integer::operator< (const Integer& other) const noexcept {
  if (_sig > other._sig)
    return false;
  if (_sig < other._sig)
    return true;
  if (_sig == 0)
    return false;
  auto op1 = _num;
  auto op2 = other._num;
  return _sig * __cmp(op1->data, op1->size, op2->data, op2->size) < 0;
}

bool Integer::operator<= (const Integer& other) const noexcept {
  if (_sig > other._sig)
    return false;
  if (_sig < other._sig)
    return true;
  if (_sig == 0)
    return true;
  auto op1 = _num;
  auto op2 = other._num;
  return _sig * __cmp(op1->data, op1->size, op2->data, op2->size) <= 0;
}

bool Integer::operator> (const Integer& other) const noexcept {
  if (_sig > other._sig)
    return true;
  if (_sig < other._sig)
    return false;
  if (_sig == 0)
    return false;
  auto op1 = _num;
  auto op2 = other._num;
  return _sig * __cmp(op1->data, op1->size, op2->data, op2->size) > 0;
}

bool Integer::operator>= (const Integer& other) const noexcept {
  if (_sig > other._sig)
    return true;
  if (_sig < other._sig)
    return false;
  if (_sig == 0)
    return true;
  auto op1 = _num;
  auto op2 = other._num;
  return _sig * __cmp(op1->data, op1->size, op2->data, op2->size) >= 0;
}


IntegerQR Integer::div_mod (const Integer& op1, const Integer& op2) {
  if (!op2._sig)
    throw "divide by 0";
  if (!op1._sig)
    return {{}, {}};
  auto sign = op1._sig * op2._sig;
  if (op2._num == &__One)
    return {{op1._num, sign}, {}};
  auto num1 = op1._num;
  auto num2 = op2._num;
  auto res = __cmp(num1->data, num1->size, num2->data, num2->size);
  if (res < 0)
    return {{}, op1};
  if (res == 0)
    return {__one(sign), {}};
  auto div = Num::allocate(num1->size - num2->size + 1);
  auto mod = Num::allocate(num2->size);
  if (num2->size == 1) {
    __div(div->data, num1->data, num1->size, num2->data[0]);
    mod->data[0] = __div(nullptr, num1->data, num1->size, num2->data[0]);
    mod->size = 1;
  }
  else {
    __div(div->data, mod->data, num1->data, num1->size, num2->data, num2->size);
    mod->size = num2->size;
  }
  div->shrink(num1->size - num2->size + 1);
  mod->shrink(mod->size);
  return {{div, sign, false}, {mod, mod->size ? op1._sig : 0, false}};
}


CLOSE_JLIB_NS






#include <jni.h>

USE_JLIB_NS

#define JNI_METHOD(return_value, name) JNIEXPORT return_value JNICALL Java_CInteger_ ## name


inline static Integer* fromJavaString (JNIEnv* jenv, jstring jsrc) {
  auto len = (u32)jenv->GetStringUTFLength(jsrc);
  auto src = jenv->GetStringUTFChars(jsrc, nullptr);
  auto dst = new Integer(src, len);
  jenv->ReleaseStringUTFChars(jsrc, src);
  return dst;
}


extern "C" {

JNI_METHOD(jlong, nnew) (JNIEnv* jenv, jclass jcls, jstring jsrc) {
  return (jlong)fromJavaString(jenv, jsrc);
}

JNI_METHOD(void, ndelete) (JNIEnv* jenv, jclass jcls, jlong jref) {
  delete (Integer*)jref;
}

JNI_METHOD(jint, ncmp) (JNIEnv* jenv, jclass jcls, jlong jop1, jlong jop2) {
  auto op1 = (Integer*)jop1;
  auto op2 = (Integer*)jop2;
  auto res = op1->cmp(*op2);
  return (jint)res;
}

JNI_METHOD(jlong, nadd) (JNIEnv* jenv, jclass jcls, jlong jop1, jlong jop2) {
  auto op1 = (Integer*)jop1;
  auto op2 = (Integer*)jop2;
  auto res = op1->operator+(*op2);
  return (jlong)new Integer(res);
}

JNI_METHOD(jlong, nsub) (JNIEnv* jenv, jclass jcls, jlong jop1, jlong jop2) {
  auto op1 = (Integer*)jop1;
  auto op2 = (Integer*)jop2;
  auto res = op1->operator-(*op2);
  return (jlong)new Integer(res);
}

JNI_METHOD(jlong, nmul) (JNIEnv* jenv, jclass jcls, jlong jop1, jlong jop2) {
  auto op1 = (Integer*)jop1;
  auto op2 = (Integer*)jop2;
  auto res = op1->operator*(*op2);
  return (jlong)new Integer(res);
}

JNI_METHOD(jlong, ndiv) (JNIEnv* jenv, jclass jcls, jlong jop1, jlong jop2) {
  auto op1 = (Integer*)jop1;
  auto op2 = (Integer*)jop2;
  auto res = op1->operator/(*op2);
  return (jlong)new Integer(res);
}

JNI_METHOD(jlong, nmod) (JNIEnv* jenv, jclass jcls, jlong jop1, jlong jop2) {
  auto op1 = (Integer*)jop1;
  auto op2 = (Integer*)jop2;
  auto res = op1->operator%(*op2);
  if (res.sign() < 0)
    res = res + *op2;
  return (jlong)new Integer(res);
}

JNI_METHOD(jlong, nneg) (JNIEnv* jenv, jclass jcls, jlong jref) {
  auto ref = (Integer*)jref;
  auto res = ref->operator-();
  return (jlong)new Integer(res);
}

JNI_METHOD(jlong, nabs) (JNIEnv* jenv, jclass jcls, jlong jref) {
  auto ref = (Integer*)jref;
  auto res = ref->abs();
  return (jlong)new Integer(res);
}

JNI_METHOD(jlong, npow) (JNIEnv* jenv, jclass jcls, jlong jref, jint jexp) {
  auto ref = (Integer*)jref;
  auto exp = (u32)jexp;
  auto res = ref->pow(exp);
  return (jlong)new Integer(res);
}

JNI_METHOD(jobject, nmeta) (JNIEnv* jenv, jclass jcls, jlong jref) {
  auto ref = (Integer*)jref;
  auto cls = jenv->FindClass("Integer$Meta");
  auto method = jenv->GetMethodID(cls, "<init>", "()V");
  auto obj = jenv->NewObject(cls, method);
  auto field1 = jenv->GetFieldID(cls, "sign", "I");
  jenv->SetIntField(obj, field1, (jint)ref->sign());
  auto field2 = jenv->GetFieldID(cls, "value", "Ljava/lang/String;");
  auto str = ref->str();
  jenv->SetObjectField(obj, field2, jenv->NewStringUTF(str.c_str()));
  return obj;
}

JNI_METHOD(jlong, ncount) (JNIEnv* jenv, jclass jcls) {
  return (jlong)Integer::__counter;
}

JNI_METHOD(jlong, nbuffers) (JNIEnv* jenv, jclass jcls) {
  return (jlong)Integer::Num::__counter;
}

}